// Created by WXX on 2021/8/24 9:52
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

/**
 * 执行用时：24 ms, 在所有 C++ 提交中击败了90.08%的用户
 * 内存消耗：11.8 MB, 在所有 C++ 提交中击败了100.00%的用户
 */
class Solution {
public:
    static const int N = 110, INF = 0x3f3f3f3f;
    int dist[N], backup[N];

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        memset(dist, 0x3f, sizeof dist);
        dist[src] = 0;
        for (int i = 0; i <= k; i++) {
            memcpy(backup, dist, sizeof dist);
            for (auto &edge : flights) {
                int a = edge[0], b = edge[1], w = edge[2];
                dist[b] = min(dist[b], backup[a] + w);
            }
        }
        if (dist[dst] > INF / 2) return -1;
        return dist[dst];
    }
};

int main() {

    vector<vector<int>> flights = {
            {0, 1, 100},
            {1, 2, 100},
            {0, 2, 500}
    };
    cout << Solution().findCheapestPrice(3, flights, 0, 2, 1) << endl;

    return 0;
}
